10947. Со мной снова медведь
Лари со своим другом Районом
хотят перебраться с острова, на котором обитают медведи, на тот, на котором их
нет. При этом в море существуют еще и другие острова с медведями. У Лари есть
плот, способный передвигаться со скоростью M миль в день. Поскольку плот сделан
некачественно, то в пути он может находиться не более K дней. Не позднее чем
через K дней плот следует швартовать к какому-нибудь острову и ремонтировать,
после чего можно снова отправляться в путь. Необходимо определить, смогут ли Лари
с Районом спастись от медведей.
Вход.
Состоит из нескольких тестов. Первая строка каждого теста содержит два числа K
и M. Вторая строка содержит координаты x, y и радиус острова, на
котором изначально находится Лари. Третья строка содержит координаты и радиус
безопасного острова, на который Лари желает перебраться. Четвертая строка
содержит число других островов n (n £ 100) с
медведями в море. Следующие n строк содержат координаты и радиусы этих
островов. Все величины заданы в милях.
Выход. Для каждого теста выяснить,
смогут ли Лари с Районом перебраться на желаемый остров. В случае удачного
завершения плавания вывести сообщение “Larry and Ryan will escape!”, иначе
вывести “Larry and Ryan will be eaten to death.”.
1 1
0 0 1
0 3 1
0
1 1
0 0 1
0 5 1
0
1 1
0 0 1
0 6 1
1
0 3 1
Пример выхода
Larry and Ryan will escape!
Larry and Ryan will be eaten to death.
Larry and Ryan will escape!
поиск в глубину, достижимость вершины в
графе
(xi
– xj)2 + (yi – yj)2
£ (ri + rj + k *
m)2
Во всех тестах максимальное
расстояние, которое Лари с Районом могут преодолеть, равно 1 * 1 = 1 миля. Во
втором тесте имеются лишь начальный и конечный острова, расстояние между
которыми равно 3. Это расстояние без помощи других островов преодолеть невозможно.
В третьем тесте между исходным и конечным островом лежит еще один остров.
Друзья могут спастись, для этого им надо добраться с начального острова на
третий (расстояние между ними равно 1) и починить там плот, а потом плыть к
желаемому острову, расстояние до которого равно 1.
В переменной MAX содержится
максимально возможное общее число островов, оно равно 100 плюс 2 (остров, на
котором изначально находится Лари и остров без медведей, на который следует
попасть). В массивах x, y, r хранятся координаты островов
и их радиусы. Массив used используется при поиске в глубину.
#define MAX 102
int x[MAX], y[MAX], r[MAX];
int used[MAX];
Функция cango возвращает 1, если Лари
может непосредственно перебраться с острова i на остров j. Он
может это сделать, если расстояние между островами не больше суммы их радиусов
и пути, который Лари может преодолеть без починки плота (он равен k * m).
int cango(int
i, int j)
{
int temp =
(x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]);
if (temp >
(r[i] + r[j] + k*m) * (r[i] + r[j] + k*m)) return
0;
return 1;
}
Поиск в глубину производится
функцией dfs.
void dfs(int
i)
{
int j;
used[i] = 1;
for(j = 0; j
< n + 2; j++)
if
(!used[j] && cango(i,j)) dfs(j);
}
Читаем входные данные. Данные
начального острова заносим в массивы с индексом 0, конечного – в массивы с
индексом 1.
while(scanf("%d
%d",&k,&m) == 2)
{
for(i = 0; i
< 2; i++)
scanf("%d
%d %d",&x[i],&y[i],&r[i]);
scanf("%d",&n);
for(i = 2; i
< 2 + n; i++)
scanf("%d %d %d",&x[i],&y[i],&r[i]);
Изначально положим все острова не
просмотренными, присвоим used[i] = 0. Вызов функции dfs(0) положит used[i]
= 1 для всех островов i, достижимых с нулевого (начального).
memset(used,0,sizeof(used));
dfs(0);
Если used[1] = 1, то конечный
остров, куда следует перебраться Лари, достижим с нулевого, то есть можно
удрать от медведей. Иначе Лари погибнет.
if (used[1])
printf("Larry and Ryan will escape!\n");
else
printf("Larry and Ryan will be eaten to
death.\n");
}